<?xml version="1.0" encoding="utf-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
  "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" xmlns:xml="http://www.w3.org/XML/1998/namespace">
<head>
  <meta content="width=device-width, initial-scale=1.0" name="viewport" />
  <meta content="$Id: freertos.html 1340 2012-04-26 14:40:43Z amy $" name="provenance" />
  <link href="../Styles/bootstrap.css" rel="stylesheet" type="text/css" />
  <link href="../Styles/bootstrap-responsive.css" rel="stylesheet" type="text/css" />
  <link href="../Styles/aosa.css" rel="stylesheet" type="text/css" />

  <title>The Architecture of Open Source Applications (Volume 2): FreeRTOS</title>
</head>

<body>
  <div class="container row-fluid hero-unit">
    <h1 id="heading_id_2">FreeRTOS</h1>

    <p><a href="../Text/intro2.html#svec-christopher">Christopher Svec</a></p>
  </div>

  <p>FreeRTOS (pronounced "free-arr-toss") is an open source real-time operating system (RTOS) for embedded systems. <a href="http://www.freertos.org/index.html?http://www.freertos.org/FreeRTOS_Features.html">FreeRTOS</a> supports many different architectures and compiler toolchains, and is designed to be "small, simple, and easy to use".</p>

  <p>FreeRTOS is under active development, and has been since Richard Barry started work on it in 2002. As for me, I'm not a developer of or contributor to FreeRTOS, I'm merely a user and a fan. As a result, this chapter will favor the "what" and "how" of FreeRTOS's architecture, with less of the "why" than other chapters in this book.</p>

  <p>Like all operating systems, FreeRTOS's main job is to run tasks. Most of FreeRTOS's code involves prioritizing, scheduling, and running user-defined tasks. Unlike all operating systems, FreeRTOS is a real-time operating system which runs on embedded systems.</p>

  <p>By the end of this chapter I hope that you'll understand the basic architecture of FreeRTOS. Most of FreeRTOS is dedicated to running tasks, so you'll get a good look at exactly how FreeRTOS does that.</p>

  <p>If this is your first look under the hood of an operating system, I also hope that you'll learn the basics about how any OS works. FreeRTOS is relatively simple, especially when compared to Windows, Linux, or OS X, but all operating systems share the same basic concepts and goals, so looking at any OS can be instructive and interesting.</p>

  <h2 id="heading_id_3">3.1. What is "Embedded" and "Real-Time"?</h2>

  <p>"Embedded" and "real-time" can mean different things to different people, so let's define them as FreeRTOS uses them.</p>

  <p>An embedded system is a computer system that is designed to do only a few things, like the system in a TV remote control, in-car GPS, digital watch, or pacemaker. Embedded systems are typically smaller and slower than general purpose computer systems, and are also usually less expensive. A typical low-end embedded system may have an 8-bit CPU running at 25MHz, a few KB of RAM, and maybe 32KB of flash memory. A higher-end embedded system may have a 32-bit CPU running at 750MHz, a GB of RAM, and multiple GB of flash memory.</p>

  <p>Real-time systems are designed to do something within a certain amount of time; they guarantee that stuff happens when it's supposed to.</p>

  <p>A pacemaker is an excellent example of a real-time embedded system. A pacemaker must contract the heart muscle at the right time to keep you alive; it can't be too busy to respond in time. Pacemakers and other real-time embedded systems are carefully designed to run their tasks on time, every time.</p>

  <h2 id="heading_id_4">3.2. Architecture Overview</h2>

  <p>FreeRTOS is a relatively small application. The minimum core of FreeRTOS is only three source (<code>.c</code>) files and a handful of header files, totalling just under 9000 lines of code, including comments and blank lines. A typical binary code image is less than 10KB.</p>

  <p>FreeRTOS's code breaks down into three main areas: tasks, communication, and hardware interfacing.</p>

  <ul>
    <li><strong>Tasks:</strong> Almost half of FreeRTOS's core code deals with the central concern in many operating systems: tasks. A task is a user-defined C function with a given priority. <code>tasks.c</code> and <code>task.h</code> do all the heavy lifting for creating, scheduling, and maintaining tasks.</li>

    <li><strong>Communication:</strong> Tasks are good, but tasks that can communicate with each other are even better! Which brings us to the second FreeRTOS job: communication. About 40% of FreeRTOS's core code deals with communication. <code>queue.c</code> and <code>queue.h</code> handle FreeRTOS communication. Tasks and interrupts use queues to send data to each other and to signal the use of critical resources using semaphores and mutexes.</li>

    <li><strong>The Hardware Whisperer:</strong> The approximately 9000 lines of code that make up the base of FreeRTOS are hardware-independent; the same code runs whether FreeRTOS is running on the humble 8051 or the newest, shiniest ARM core. About 6% of FreeRTOS's core code acts a shim between the hardware-independent FreeRTOS core and the hardware-dependent code. We'll discuss the hardware-dependent code in the next section.</li>
  </ul>

  <h3 id="heading_id_5">Hardware Considerations</h3>

  <p>The hardware-independent FreeRTOS layer sits on top of a hardware-dependent layer. This hardware-dependent layer knows how to talk to whatever chip architecture you choose. <a href="#fig.freertos.layers">Figure 3.1</a> shows FreeRTOS's layers.</p>

  <div class="figure" id="fig.freertos.layers">
    <img alt="" src="../Images/freertos-figures-layers.png" />

    <p>Figure 3.1: FreeRTOS software layers</p>
  </div>

  <p>FreeRTOS ships with all the hardware-independent as well as hardware-dependent code you'll need to get a system up and running. It supports many compilers (CodeWarrior, GCC, IAR, etc.) as well as many processor architectures (ARM7, ARM Cortex-M3, various PICs, Silicon Labs 8051, x86, etc.). See the FreeRTOS website for a list of supported architectures and compilers.</p>

  <p>FreeRTOS is highly configurable by design. FreeRTOS can be built as a single CPU, bare-bones RTOS, supporting only a few tasks, or it can be built as a highly functional multicore beast with TCP/IP, a file system, and USB.</p>

  <p>Configuration options are selected in <code>FreeRTOSConfig.h</code> by setting various <code>#defines</code>. Clock speed, heap size, mutexes, and API subsets are all configurable in this file, along with many other options. Here are a few examples that set the maximum number of task priority levels, the CPU frequency, the system tick frequency, the minimal stack size and the total heap size:</p>
  <pre>
#define configMAX_PRIORITIES ((unsigned portBASE_TYPE) 5)
#define configCPU_CLOCK_HZ        (12000000UL)
#define configTICK_RATE_HZ       ((portTickType) 1000)
#define configMINIMAL_STACK_SIZE ((unsigned short) 100)
#define configTOTAL_HEAP_SIZE    ((size_t) (4 * 1024))
</pre>

  <p>Hardware-dependent code lives in separate files for each compiler toolchain and CPU architecture. For example, if you're working with the IAR compiler on an ARM Cortex-M3 chip, the hardware-dependent code lives in the <code>FreeRTOS/Source/portable/IAR/ARM_CM3/</code> directory. <code>portmacro.h</code> declares all of the hardware-specific functions, while <code>port.c</code> and <code>portasm.s</code> contain all of the actual hardware-dependent code. The hardware-independent header file <code>portable.h</code> <code>#include</code>'s the correct <code>portmacro.h</code> file at compile time. FreeRTOS calls the hardware-specific functions using <code>#define</code>'d functions declared in <code>portmacro.h</code>.</p>

  <p>Let's look at an example of how FreeRTOS calls a hardware-dependent function. The hardware-independent file <code>tasks.c</code> frequently needs to enter a critical section of code to prevent preemption. Entering a critical section happens differently on different architectures, and the hardware-independent <code>tasks.c</code> does not want to have to understand the hardware-dependent details. So <code>tasks.c</code> calls the global macro <code>portENTER_CRITICAL()</code>, glad to be ignorant of how it actually works. Assuming we're using the IAR compiler on an ARM Cortex-M3 chip, FreeRTOS is built with the file <code>FreeRTOS/Source/portable/IAR/ARM_CM3/portmacro.h</code> which defines <code>portENTER_CRITICAL()</code> like this:</p>
  <pre>
#define portENTER_CRITICAL()   vPortEnterCritical()
</pre>

  <p><code>vPortEnterCritical()</code> is actually defined in <code>FreeRTOS/Source/portable/IAR/ARM_CM3/port.c</code>. The <code>port.c</code> file is hardware-dependent, and contains code that understands the IAR compiler and the Cortex-M3 chip. <code>vPortEnterCritical()</code> enters the critical section using this hardware-specific knowledge and returns to the hardware-independent <code>tasks.c</code>.</p>

  <p>The <code>portmacro.h</code> file also defines an architecture's basic data types. Data types for basic integer variables, pointers, and the system timer tick data type are defined like this for the IAR compiler on ARM Cortex-M3 chips:</p>
  <pre>
// Basic integer variable type
#define portBASE_TYPE  long
// Pointers to memory locations
#define portSTACK_TYPE unsigned long
// The system timer tick type
typedef unsigned portLONG portTickType;
</pre>

  <p>This method of using data types and functions through thin layers of <code>#defines</code> may seem a bit complicated, but it allows FreeRTOS to be recompiled for a completely different system architecture by changing only the hardware-dependent files. And if you want to run FreeRTOS on an architecture it doesn't currently support, you only have to implement the hardware-dependent functionality which is much smaller than the hardware-independent part of FreeRTOS.</p>

  <p>As we've seen, FreeRTOS implements hardware-dependent functionality with C preprocessor <code>#define</code> macros. FreeRTOS also uses <code>#define</code> for plenty of hardware-independent code. For non-embedded applications this frequent use of <code>#define</code> is a cardinal sin, but in many smaller embedded systems the overhead for calling a function is not worth the advantages that "real" functions offer.</p>

  <h2 id="heading_id_6">3.3. Scheduling Tasks: A Quick Overview</h2>

  <h3 id="heading_id_7">Task Priorities and the Ready List</h3>

  <p>Each task has a user-assigned priority between 0 (the lowest priority) and the compile-time value of <code>configMAX_PRIORITIES-1</code> (the highest priority). For instance, if <code>configMAX_PRIORITIES</code> is set to 5, then FreeRTOS will use 5 priority levels: 0 (lowest priority), 1, 2, 3, and 4 (highest priority).</p>

  <p>FreeRTOS uses a "ready list" to keep track of all tasks that are currently ready to run. It implements the ready list as an array of task lists like this:</p>
  <pre>
/* Prioritised ready tasks.  */
static xList pxReadyTasksLists[ configMAX_PRIORITIES ];
</pre>

  <p><code>pxReadyTasksLists[0]</code> is a list of all ready priority 0 tasks, <code>pxReadyTasksLists[1]</code> is a list of all ready priority 1 tasks, and so on, all the way up to <code>pxReadyTasksLists[configMAX_PRIORITIES-1]</code>.</p>

  <h3 id="heading_id_8">The System Tick</h3>

  <p>The heartbeat of a FreeRTOS system is called the system tick. FreeRTOS configures the system to generate a periodic tick interrupt. The user can configure the tick interrupt frequency, which is typically in the millisecond range. Every time the tick interrupt fires, the <code>vTaskSwitchContext()</code> function is called. <code>vTaskSwitchContext()</code> selects the highest-priority ready task and puts it in the <code>pxCurrentTCB</code> variable like this:</p>
  <pre>
/* Find the highest-priority queue that contains
   ready tasks. */
while( listLIST_IS_EMPTY( &amp;( pxReadyTasksLists[ uxTopReadyPriority ] ) ) )
{
    configASSERT( uxTopReadyPriority );
    --uxTopReadyPriority;
}

/* listGET_OWNER_OF_NEXT_ENTRY walks through the
   list, so the tasks of the same priority get an 
   equal share of the processor time. */
listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &amp;( pxReadyTasksLists[ uxTopReadyPriority ] ) );
</pre>

  <p>Before the while loop starts, <code>uxTopReadyPriority</code> is guaranteed to be greater than or equal to the priority of the highest-priority ready task. The while() loop starts at priority level <code>uxTopReadyPriority</code> and walks down through the <code>pxReadyTasksLists[]</code> array to find the highest-priority level with ready tasks. <code>listGET_OWNER_OF_NEXT_ENTRY()</code> then grabs the next ready task from that priority level's ready list.</p>

  <p>Now <code>pxCurrentTCB</code> points to the highest-priority task, and when <code>vTaskSwitchContext()</code> returns the hardware-dependent code starts running that task.</p>

  <p>Those nine lines of code are the absolute heart of FreeRTOS. The other 8900+ lines of FreeRTOS are there to make sure those nine lines are all that's needed to keep the highest-priority task running.</p>

  <p><a href="#fig.freertos.ready">Figure 3.2</a> is a high-level picture of what a ready list looks like. This example has three priority levels, with one priority 0 task, no priority 1 tasks, and three priority 2 tasks. This picture is accurate but not complete; it's missing a few details which we'll fill in later.</p>

  <div class="figure" id="fig.freertos.ready">
    <img alt="" src="../Images/freertos-figures-basic-ready-list.png" />

    <p>Figure 3.2: Basic view of FreeRTOS Ready List</p>
  </div>

  <p>Now that we have the high-level overview out of the way, let's dive in to the details. We'll look at the three main FreeRTOS data structures: tasks, lists, and queues.</p>

  <h2 id="heading_id_9">3.4. Tasks</h2>

  <p>The main job of all operating systems is to run and coordinate user tasks. Like many operating systems, the basic unit of work in FreeRTOS is the task. FreeRTOS uses a Task Control Block (TCB) to represent each task.</p>

  <h3 id="heading_id_10">Task Control Block (TCB)</h3>

  <p>The TCB is defined in <code>tasks.c</code> like this:</p>
  <pre>
typedef struct tskTaskControlBlock
{
  /* Points to the location of the last item placed on
     the tasks stack.  THIS MUST BE THE FIRST MEMBER
     OF THE STRUCT. */
   volatile portSTACK_TYPE *pxTopOfStack;

  /* List item used to place the TCB in ready and
     blocked queues. */
  xListItem    xGenericListItem;
    
  /* List item used to place the TCB in event lists.*/
  xListItem    xEventListItem;

  /* The priority of the task where 0 is the lowest
     priority. */
  unsigned portBASE_TYPE uxPriority;
       
  /* Points to the start of the stack. */
  portSTACK_TYPE *pxStack;

  /* Descriptive name given to the task when created.
     Facilitates debugging only. */
  signed char    pcTaskName[ configMAX_TASK_NAME_LEN ];

  /* Used for stack overflow checking on architectures
     where the stack grows up from low memory. */
  #if ( portSTACK_GROWTH &gt; 0 )
    portSTACK_TYPE *pxEndOfStack;          
  #endif

  #if ( configUSE_MUTEXES == 1 )
    /* The priority last assigned to the task
       used by the priority inheritance mechanism. */
    unsigned portBASE_TYPE uxBasePriority;
  #endif

} tskTCB;
</pre>

  <p>The TCB stores the address of the stack start address in <code>pxStack</code> and the current top of stack in <code>pxTopOfStack</code>. It also stores a pointer to the end of the stack in <code>pxEndOfStack</code> to check for stack overflow if the stack grows "up" to higher addresses. If the stack grows "down" to lower addresses then stack overflow is checked by comparing the current top of stack against the start of stack memory in <code>pxStack</code>.</p>

  <p>The TCB stores the initial priority of the task in <code>uxPriority</code> and <code>uxBasePriority</code>. A task is given a priority when it is created, and a task's priority can be changed. If FreeRTOS implements priority inheritance then it uses <code>uxBasePriority</code> to remember the original priority while the task is temporarily elevated to the "inherited" priority. (See the discussion about mutexes below for more on priority inheritance.)</p>

  <p>Each task has two list items for use in FreeRTOS's various scheduling lists. When a task is inserted into a list FreeRTOS doesn't insert a pointer directly to the TCB. Instead, it inserts a pointer to either the TCB's <code>xGenericListItem</code> or <code>xEventListItem</code>. These <code>xListItem</code> variables let the FreeRTOS lists be smarter than if they merely held a pointer to the TCB. We'll see an example of this when we discuss lists later.</p>

  <p>A task can be in one of four states: running, ready to run, suspended, or blocked. You might expect each task to have a variable that tells FreeRTOS what state it's in, but it doesn't. Instead, FreeRTOS tracks task state implicitly by putting tasks in the appropriate list: ready list, suspended list, etc. The presence of a task in a particular list indicates the task's state. As a task changes from one state to another, FreeRTOS simply moves it from one list to another.</p>

  <h3 id="heading_id_11">Task Setup</h3>

  <p>We've already touched on how a task is selected and scheduled with the <code>pxReadyTasksLists</code> array; now let's look at how a task is initially created. A task is created when the <code>xTaskCreate()</code> function is called. FreeRTOS uses a newly allocated TCB object to store the name, priority, and other details for a task, then allocates the amount of stack the user requests (assuming there's enough memory available) and remembers the start of the stack memory in TCB's <code>pxStack</code> member.</p>

  <p>The stack is initialized to look as if the new task is already running and was interrupted by a context switch. This way the scheduler can treat newly created tasks exactly the same way as it treats tasks that have been running for a while; the scheduler doesn't need any special case code for handling new tasks.</p>

  <p>The way that a task's stack is made to look like it was interrupted by a context switch depends on the architecture FreeRTOS is running on, but this ARM Cortex-M3 processor's implementation is a good example:</p>
  <pre>
unsigned int *pxPortInitialiseStack(
                         unsigned int *pxTopOfStack, 
                         pdTASK_CODE pxCode,
                         void *pvParameters )
{
  /* Simulate the stack frame as it would be created
     by a context switch interrupt. */

  /* Offset added to account for the way the MCU uses
     the stack on entry/exit of interrupts. */
  pxTopOfStack--;
  /* xPSR */
  *pxTopOfStack = portINITIAL_XPSR;
  pxTopOfStack--;
  /* PC */
  *pxTopOfStack = ( portSTACK_TYPE ) pxCode;
  pxTopOfStack--;
  /* LR */
  *pxTopOfStack = 0;
  /* R12, R3, R2 and R1. */
  pxTopOfStack -= 5;
  /* R0 */
  *pxTopOfStack = ( portSTACK_TYPE ) pvParameters;
  /* R11, R10, R9, R8, R7, R6, R5 and R4. */
  pxTopOfStack -= 8;
  
  return pxTopOfStack;
}
</pre>

  <p>The ARM Cortex-M3 processor pushes registers on the stack when a task is interrupted. <code>pxPortInitialiseStack()</code> modifies the stack to look like the registers were pushed even though the task hasn't actually started running yet. Known values are stored to the stack for the ARM registers <code>xPSR, PC, LR,</code> and <code>R0</code>. The remaining registers <code>R1</code> -- <code>R12</code> get stack space allocated for them by decrementing the top of stack pointer, but no specific data is stored in the stack for those registers. The ARM architecture says that those registers are undefined at reset, so a (non-buggy) program will not rely on a known value.</p>

  <p>After the stack is prepared, the task is almost ready to run. First though, FreeRTOS disables interrupts: We're about to start mucking with the ready lists and other scheduler structures and we don't want anyone else changing them underneath us.</p>

  <p>If this is the first task to ever be created, FreeRTOS initializes the scheduler's task lists. FreeRTOS's scheduler has an array of ready lists, <code>pxReadyTasksLists[]</code>, which has one ready list for each possible priority level. FreeRTOS also has a few other lists for tracking tasks that have been suspended, killed, and delayed. These are all initialized now as well.</p>

  <p>After any first-time initialization is done, the new task is added to the ready list at its specified priority level. Interrupts are re-enabled and new task creation is complete.</p>

  <h2 id="heading_id_12">3.5. Lists</h2>

  <p>After tasks, the most used FreeRTOS data structure is the list. FreeRTOS uses its list structure to keep track of tasks for scheduling, and also to implement queues.</p>

  <div class="figure" id="fig.freertos.list">
    <img alt="" src="../Images/freertos-figures-full-ready-list.png" />

    <p>Figure 3.3: Full view of FreeRTOS Ready List</p>
  </div>

  <p>The FreeRTOS list is a standard circular doubly linked list with a couple of interesting additions. Here's a list element:</p>
  <pre>
struct xLIST_ITEM
{
  /* The value being listed.  In most cases this
     is used to sort the list in descending order. */
  portTickType xItemValue;

  /* Pointer to the next xListItem in the list. */
  volatile struct xLIST_ITEM * pxNext;  

  /* Pointer to the previous xListItem 
    in the list. */
  volatile struct xLIST_ITEM * pxPrevious;   

  /* Pointer to the object (normally a TCB) that
     contains the list item.  There is therefore a
     two-way link between the object containing
     the list item and the list item itself. */
  void * pvOwner;

  /* Pointer to the list in which this list
     item is placed (if any). */
  void * pvContainer;
};
</pre>

  <p>Each list element holds a number, <code>xItemValue</code>, that is the usually the priority of the task being tracked or a timer value for event scheduling. Lists are kept in high-to-low priority order, meaning that the highest-priority <code>xItemValue</code> (the largest number) is at the front of the list and the lowest priority <code>xItemValue</code> (the smallest number) is at the end of the list.</p>

  <p>The <code>pxNext</code> and <code>pxPrevious</code> pointers are standard linked list pointers. <code>pvOwner</code> is a pointer to the owner of the list element. This is usually a pointer to a task's TCB object. <code>pvOwner</code> is used to make task switching fast in <code>vTaskSwitchContext()</code>: once the highest-priority task's list element is found in <code>pxReadyTasksLists[]</code>, that list element's <code>pvOwner</code> pointer leads us directly to the TCB needed to schedule the task.</p>

  <p><code>pvContainer</code> points to the list that this item is in. It is used to quickly determine if a list item is in a particular list. Each list element can be put in a list, which is defined as:</p>
  <pre>
typedef struct xLIST
{
  volatile unsigned portBASE_TYPE uxNumberOfItems;

  /* Used to walk through the list.  Points to
     the last item returned by a call to 
     pvListGetOwnerOfNextEntry (). */
  volatile xListItem * pxIndex;

  /* List item that contains the maximum possible
     item value, meaning it is always at the end of
     the list and is therefore used as a marker. */
  volatile xMiniListItem xListEnd;

} xList;
</pre>

  <p>The size of a list at any time is stored in <code>uxNumberOfItems</code>, for fast list-size operations. All new lists are initialized to contain a single element: the <code>xListEnd</code> element. <code>xListEnd.xItemValue</code> is a sentinel value which is equal to the largest value for the <code>xItemValue</code> variable: <code>0xffff</code> when <code>portTickType</code> is a 16-bit value and <code>0xffffffff</code> when <code>portTickType</code> is a 32-bit value. Other list elements may also have the same value; the insertion algorithm ensures that <code>xListEnd</code> is always the last item in the list.</p>

  <p>Since lists are sorted high-to-low, the <code>xListEnd</code> element is used as a marker for the start of the list. And since the list is circular, this <code>xListEnd</code> element is also a marker for the end of the list.</p>

  <p>Most "traditional" list accesses you've used probably do all of their work within a single for() loop or function call like this:</p>
  <pre>
for (listPtr = listStart; listPtr != NULL;
                 listPtr = listPtr-&gt;next) {
  // Do something with listPtr here...
}
</pre>

  <p>FreeRTOS frequently needs to access a list across multiple for() and while() loops as well as function calls, and so it uses list functions that manipulate the <code>pxIndex</code> pointer to walk the list. The list function <code>listGET_OWNER_OF_NEXT_ENTRY()</code> does <code>pxIndex = pxIndex-&gt;pxNext;</code> and returns <code>pxIndex</code>. (Of course it does the proper end-of-list-wraparound detection too.) This way the list itself is responsible for keeping track of "where you are" while walking it using <code>pxIndex</code>, allowing the rest of FreeRTOS to not worry about it.</p>

  <div class="figure" id="fig.freertos.aftertick">
    <img alt="" src="../Images/freertos-figures-full-ready-list-2.png" />

    <p>Figure 3.4: Full view of FreeRTOS Ready List after a system timer tick</p>
  </div>

  <p>The <code>pxReadyTasksLists[]</code> list manipulation done in <code>vTaskSwitchContext()</code> is a good example of how <code>pxIndex</code> is used. Let's assume we have only one priority level, priority 0, and there are three tasks at that priority level. This is similar to the basic ready list picture we looked at earlier, but this time we'll include all of the data structures and fields.</p>

  <p>As you can see in <a href="#fig.freertos.list">Figure 3.3</a>, <code>pxCurrentTCB</code> indicates that we're currently running Task B. The next time <code>vTaskSwitchContext()</code> runs, it calls <code>listGET_OWNER_OF_NEXT_ENTRY()</code> to get the next task to run. This function uses <code>pxIndex-&gt;pxNext</code> to figure out the next task is Task C, and now <code>pxIndex</code> points to Task C's list element and <code>pxCurrentTCB</code> points to Task C's TCB, as shown in <a href="#fig.freertos.aftertick">Figure 3.4</a>.</p>

  <p>Note that each <code>struct xListItem</code> object is actually the <code>xGenericListItem</code> object from the associated TCB.</p>

  <h2 id="heading_id_13">3.6. Queues</h2>

  <p>FreeRTOS allows tasks to communicate and synchronize with each other using queues. Interrupt service routines (ISRs) also use queues for communication and synchronization.</p>

  <p>The basic queue data structure is:</p>
  <pre>
typedef struct QueueDefinition
{
  /* Points to the beginning of the queue storage
     area. */
  signed char *pcHead;

 /* Points to the byte at the end of the queue
    storage area. One more byte is allocated than
    necessary to store the queue items; this is
    used as a marker. */                
  signed char *pcTail;

  /* Points to the free next place in the storage
     area. */
  signed char *pcWriteTo;

  /* Points to the last place that a queued
     item was read from. */
  signed char *pcReadFrom;

  /* List of tasks that are blocked waiting to post
     onto this queue. Stored in priority order. */
  xList xTasksWaitingToSend;

 /* List of tasks that are blocked waiting to read
    from this queue. Stored in priority order. */
  xList xTasksWaitingToReceive;

 /* The number of items currently in the queue. */
  volatile unsigned portBASE_TYPE uxMessagesWaiting;

  /* The length of the queue defined as the number
    of items it will hold, not the number of bytes. */
  unsigned portBASE_TYPE uxLength;

 /* The size of each items that  the queue 
    will hold. */
  unsigned portBASE_TYPE uxItemSize;
                                         
} xQUEUE;
</pre>

  <p>This is a fairly standard queue with head and tail pointers, as well as pointers to keep track of where we've just read from and written to.</p>

  <p>When creating a queue, the user specifies the length of the queue and the size of each item to be tracked by the queue. <code>pcHead</code> and <code>pcTail</code> are used to keep track of the queue's internal storage. Adding an item into a queue does a deep copy of the item into the queue's internal storage.</p>

  <p>FreeRTOS makes a deep copy instead of storing a pointer to the item because the lifetime of the item inserted may be much shorter than the lifetime of the queue. For instance, consider a queue of simple integers inserted and removed using local variables across several function calls. If the queue stored pointers to the integers' local variables, the pointers would be invalid as soon as the integers' local variables went out of scope and the local variables' memory was used for some new value.</p>

  <p>The user chooses what to queue. The user can queue copies of items if the items are small, like in the simple integer example in the previous paragraph, or the user can queue pointers to the items if the items are large. Note that in both cases FreeRTOS does a deep copy: if the user chooses to queue copies of items then the queue stores a deep copy of each item; if the user chooses to queue pointers then the queue stores a deep copy of the pointer. Of course, if the user stores pointers in the queue then the user is responsible for managing the memory associated with the pointers. The queue doesn't care what data you're storing in it, it just needs to know the data's size.</p>

  <p>FreeRTOS supports blocking and non-blocking queue insertions and removals. Non-blocking operations return immediately with a "Did the queue insertion work?" or "Did the queue removal work?" status. Blocking operations are specified with a timeout. A task can block indefinitely or for a limited amount of time.</p>

  <p>A blocked task—call it Task A—will remain blocked as long as its insert/remove operation cannot complete and its timeout (if any) has not expired. If an interrupt or another task modifies the queue so that Task A's operation could complete, Task A will be unblocked. If Task A's queue operation is still possible by the time it actually runs then Task A will complete its queue operation and return "success". However, by the time Task A actually runs, it is possible that a higher-priority task or interrupt has performed yet another operation on the queue that prevents Task A from performing its operation. In this case Task A will check its timeout and either resume blocking if the timeout hasn't expired, or return with a queue operation "failed" status.</p>

  <p>It's important to note that the rest of the system keeps going while a task is blocking on a queue; other tasks and interrupts continue to run. This way the blocked task doesn't waste CPU cycles that could be used productively by other tasks and interrupts.</p>

  <p>FreeRTOS uses the <code>xTasksWaitingToSend</code> list to keep track of tasks that are blocking on inserting into a queue. Each time an element is removed from a queue the <code>xTasksWaitingToSend</code> list is checked. If a task is waiting in that list the task is unblocked.</p>

  <p>Similarly, <code>xTasksWaitingToReceive</code> keeps track of tasks that are blocking on removing from a queue. Each time a new element is inserted into a queue the <code>xTasksWaitingToReceive</code> list is checked. If a task is waiting in that list the task is unblocked.</p>

  <h3 id="heading_id_14">Semaphores and Mutexes</h3>

  <p>FreeRTOS uses its queues for communication between and within tasks. FreeRTOS also uses its queues to implement semaphores and mutexes.</p>

  <h4 id="heading_id_15">What's The Difference?</h4>

  <p>Semaphores and mutexes may sound like the same thing, but they're not. FreeRTOS implements them similarly, but they're intended to be used in different ways. How should they be used differently? Embedded systems guru Michael Barr says it best in his article, "<a href="http://www.barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore">Mutexes and Semaphores Demystified</a>":</p>

  <blockquote><p>
    The correct use of a semaphore is for signaling from one task to another. A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects. By contrast, tasks that use semaphores either signal ("send" in FreeRTOS terms) or wait ("receive" in FreeRTOS terms) &mdash; not both.
  </p></blockquote>

  <p>A mutex is used to protect a shared resource. A task acquires a mutex, uses the shared resource, then releases the mutex. No task can acquire a mutex while the mutex is being held by another task. This guarantees that only one task is allowed to use a shared resource at a time.</p>

  <p>Semaphores are used by one task to signal another task. To quote Barr's article:</p>

  <blockquote><p>
    For example, Task 1 may contain code to post (i.e., signal or increment) a particular semaphore when the "power" button is pressed and Task 2, which wakes the display, pends on that same semaphore. In this scenario, one task is the producer of the event signal; the other the consumer.
  </p></blockquote>

  <p>If you're at all in doubt about semaphores and mutexes, please check out Michael's article.</p>

  <h4 id="heading_id_16">Implementation</h4>

  <p>FreeRTOS implements an N-element semaphore as a queue that can hold N items. It doesn't store any actual data for the queue items; the semaphore just cares how many queue entries are currently occupied, which is tracked in the queue's <code>uxMessagesWaiting</code> field. It's doing "pure synchronization", as the FreeRTOS header file <code>semphr.h</code> calls it. Therefore the queue has a item size of zero bytes (<code>uxItemSize == 0</code>). Each semaphore access increments or decrements the <code>uxMessagesWaiting</code> field; no item or data copying is needed.</p>

  <p>Like a semaphore, a mutex is also implemented as a queue, but several of the <code>xQUEUE</code> struct fields are overloaded using <code>#defines</code>:</p>
  <pre>
/* Effectively make a union out of the xQUEUE structure. */
#define uxQueueType           pcHead
#define pxMutexHolder         pcTail
</pre>

  <p>Since a mutex doesn't store any data in the queue, it doesn't need any internal storage, and so the <code>pcHead</code> and <code>pcTail</code> fields aren't needed. FreeRTOS sets the <code>uxQueueType</code> field (really the <code>pcHead</code> field) to <code>0</code> to note that this queue is being used for a mutex. FreeRTOS uses the overloaded <code>pcTail</code> fields to implement priority inheritance for mutexes.</p>

  <p>In case you're not familiar with priority inheritance, I'll quote Michael Barr again to define it, this time from his article, "<a href="https://barrgroup.com/Embedded-Systems/How-To/RTOS-Priority-Inversion">Introduction to Priority Inversion</a>":</p>

  <blockquote><p>
    [Priority inheritance] mandates that a lower-priority task inherit the priority of any higher-priority task pending on a resource they share. This priority change should take place as soon as the high-priority task begins to pend; it should end when the resource is released.
  </p></blockquote>

  <p>FreeRTOS implements priority inheritance using the <code>pxMutexHolder</code> field (which is really just the overloaded-by-<code>#define</code> <code>pcTail</code> field). FreeRTOS records the task that holds a mutex in the <code>pxMutexHolder</code> field. When a higher-priority task is found to be waiting on a mutex currently taken by a lower-priority task, FreeRTOS "upgrades" the lower-priority task to the priority of the higher-priority task until the mutex is available again.</p>

  <h2 id="heading_id_17">3.7. Conclusion</h2>

  <p>We've completed our look at the FreeRTOS architecture. Hopefully you now have a good feel for how FreeRTOS's tasks run and communicate. And if you've never looked at any OS's internals before, I hope you now have a basic idea of how they work.</p>

  <p>Obviously this chapter did not cover all of FreeRTOS's architecture. Notably, I didn't mention memory allocation, ISRs, debugging, or MPU support. This chapter also did not discuss how to set up or use FreeRTOS. Richard Barry has written an excellent book, <em><a href="http://www.freertos.org/Documentation/FreeRTOS-documentation-and-book.html">Using the FreeRTOS Real Time Kernel: A Practical Guide</a></em>, which discusses exactly that; I highly recommend it if you're going to use FreeRTOS.</p>

  <h2 id="heading_id_18">3.8. Acknowledgements</h2>

  <p>I would like to thank Richard Barry for creating and maintaining FreeRTOS, and for choosing to make it open source. Richard was very helpful in writing this chapter, providing some FreeRTOS history as well as a very valuable technical review.</p>

  <p>Thanks also to Amy Brown and Greg Wilson for pulling this whole AOSA thing together.</p>

  <p>Last and most (the opposite of "not least"), thanks to my wife Sarah for sharing me with the research and writing for this chapter. Luckily she knew I was a geek when she married me!</p><!-- Localized -->
</body>
</html>
